o
Inégalité de McDiarmid :

• \(h:\mathcal Z^n\to{\Bbb R}\)
• \(h\) est tq \(\forall i\in[\![1,n]\!]\), on a $$\underset{z_i^\prime\in\mathcal Z}{\sup_{z_1,\dots,z_n\in\mathcal Z} }h(z_1,\dots,z_n)-h(z_1,\dots,z_i^\prime,\dots,z_n)=:Dh_i\leqslant c_i$$
• \((Z_1,\dots,Z_n)\) est une famille de Variables aléatoires indépendantes à valeur dans \(\mathcal Z\)

$$\Huge\iff$$

• $${\Bbb P}\big( h(Z_1,\dots,Z_n)-{\Bbb E}[h(Z_1,\dots,Z_n)]\geqslant\varepsilon\big)\leqslant e^{-2\varepsilon^2/\sum^n_{i=1}c_i^2}$$

START
Ω Basique (+inversé optionnel)
Recto: Que donne l'inégalité de McDiarmid si on prend \(h(Z_1,\dots,Z_n)=\overline Z_n\) la Moyenne empirique avec \(Z_i\overset{ps}\in[a,b]\) ?
Verso: Cela permet de retrouver l'Inégalité de Hoeffding à l'aide de l'inégalité de McDiarmid : $$c_i=\frac{b-a}n\quad\text{ et }\quad{\Bbb P}(\overline Z_n-{\Bbb E}[\overline Z_n]\geqslant\varepsilon)\leqslant e^{-2n\varepsilon^2/(b-a)^2}$$
Bonus:
Carte inversée ?: y
END
START
Ω Basique (+inversé optionnel)
Recto: Donner une fonction importante \(h\) à prendre dans l'inégalité de McDiarmid.
Verso: $$h(z_1,\dots,z_l)=\sup_{g\in\mathcal S}\left( R(g)-\frac1l\sum^n_{i=1}\rho(y_i,g(x_i))\right)\quad\text{ avec }\quad z_i=(x_i,y_i)$$par exemple avec \(\rho(y,y^\prime)=\Bbb 1_{y\ne y^\prime}\), on a \(Dh_i\leqslant\frac1l\).
Bonus: La borne est alors \(e^{-2l\varepsilon^2}\).
Carte inversée ?:
END
START
Ω Basique (+inversé optionnel)
Recto: Peut-on passer aux valeurs absolues dans l'inégalité de McDiarmid ?
Verso: Oui, il suffit de multiplier la borne par \(2\).
Bonus:
Carte inversée ?:
END